
/*******************************************************************************
 * Universidad del Valle de Guatemala
 * Algoritmos y estructuras de datos
 * Karen Tojin   08091
 * Fecha: 02 de Septiembre 2009
 * Descricion: Implementación de las colas con prioridad con uso de HEAP
 ***************************************************************************** */
/**
 *
 * @author karenAndy
 */
import java.util.Vector;
import java.util.Comparator;

public class HeapPriorityQueue<T> implements InterfacePriorityQueue<T>, Comparator<T> {

    Vector<T> heap;
    int sizeHeap, cantIn;
    boolean full;

    // post: constructs a new priority queue
    public HeapPriorityQueue(int sizeHeap) {
        this.sizeHeap = sizeHeap;
        cantIn = 0;
        heap = new Vector(sizeHeap);
    }

    // pre: value is non-null comparable
    // post: value is added to priority queue
    public void Add(T num) {
        if (cantIn >= sizeHeap) {
            full = true;
        } else {
            full = false;
            heap.add(num);
            moveUp(cantIn);
            cantIn++;
        }
    }

    // pre: !isEmpty()
    // post: returns and removes minimum value from queue
    public T Remove() {
        T minVal = heap.firstElement();
        cantIn--;
        heap.set(0, heap.get(cantIn));
        heap.setSize(heap.size() - 1);
        if (heap.size() > 1) {
            pushDownRoot(0);
        }
        return minVal;
    }

    // post: returns true if no elements are in queue
    public boolean Empty() {
        if (heap.size() == 0) {
            return true;
        }
        return false;
    }

    // post: returns true if the queue is full
    public boolean Full() {
        if (heap.size() == 1000) {
            return true;
        }
        return false;
    }

    // post: returns the result of the comparation that occur
    public int compare(T comp1, T comp2) {
        int num1 = Integer.parseInt(comp1 + "");
        int num2 = Integer.parseInt(comp2 + "");

        if (num1 > num2) {
            return 1;
        } else if (num1 < num2) {
            return -1;
        } else {
            return 0;
        }
    }

    // pre: 0 <= leaf < size
    // post: moves node at index leaf up to appropriate position
    public void moveUp(int leaf) {
        int parent = (leaf - 1) / 2;
        T value = heap.get(leaf);
        while (leaf > 0 && compare(heap.get(parent), value) == -1) {
            heap.set(leaf, heap.get(parent));
            leaf = parent;
            parent = (parent - 1) / 2;
        }
        heap.set(leaf, value);
    }

    // pre: 0 <= root < size
    // post: moves node at index root down to appropriate position in subtree
    protected void pushDownRoot(int root) {
        int mayor;
        T value = heap.get(root);
        while (root < cantIn / 2) {
            int leftChild = 2 * root + 1;
            int rightChild = leftChild + 1;
            if (rightChild < cantIn && compare(heap.get(leftChild), heap.get(rightChild)) == -1) {
                mayor = rightChild;
            } else {
                mayor = leftChild;
            }
            if (compare(value, heap.get(mayor)) >= 0) {
                break;
            }
            heap.set(root, heap.get(mayor));
            root = mayor;
        }
        heap.set(root, value);
    }
}
